package com.demo.java.OD401_450.OD442;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【查找一个有向网络的头节点和尾节点(C&D卷-200分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146326287
 */
public class OdMain {
    public static int[] findStartEndNodes(int N, int[] pairs) {
        // 构建图的入度和出度字典
        Map<Integer, Integer> inDegree = new HashMap<>();
        Map<Integer, Integer> outDegree = new HashMap<>();
        for (int i = 0; i < 2 * N; i += 2) {
            int startNode = pairs[i];
            int endNode = pairs[i + 1];
            outDegree.put(startNode, outDegree.getOrDefault(startNode, 0) + 1); // 增加起点的出度
            inDegree.put(endNode, inDegree.getOrDefault(endNode, 0) + 1); // 增加终点的入度
        }

        // 找到首节点和尾节点
        Set<Integer> startNodes = new HashSet<>(outDegree.keySet());
        startNodes.removeAll(inDegree.keySet()); // 移除所有有入度的节点

        Set<Integer> endNodes = new HashSet<>(inDegree.keySet());
        endNodes.removeAll(outDegree.keySet()); // 移除所有有出度的节点

        // 如果没有首节点或尾节点，则返回 -1
        if (startNodes.isEmpty() || endNodes.isEmpty()) {
            return new int[]{-1};
        }

        // 输出结果，尾节点按从大到小排序
        List<Integer> startList = new ArrayList<>(startNodes);
        List<Integer> endList = new ArrayList<>(endNodes);
        Collections.sort(startList); // 首节点升序排列
        Collections.sort(endList, Collections.reverseOrder()); // 尾节点降序排列

        // 合并结果
        int[] result = new int[startList.size() + endList.size()];
        for (int i = 0; i < startList.size(); i++) {
            result[i] = startList.get(i);
        }
        for (int i = 0; i < endList.size(); i++) {
            result[startList.size() + i] = endList.get(i);
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读入输入数据
        int N = scanner.nextInt();
        int[] pairs = new int[2 * N];
        for (int i = 0; i < 2 * N; i++) {
            pairs[i] = scanner.nextInt();
        }

        // 调用函数并输出结果
        int[] result = findStartEndNodes(N, pairs);
        for (int value : result) {
            System.out.print(value + " ");
        }
    }
}
